---
id: lab9-intro
slug: /labs/lab9
sidebar_position: 1
---

# 9. Ввод, сортировка и двоичный поиск в массиве структур

Алиас: `словарь`.

## Цель работы

При выполнении лабораторной работы изучить следующие вопросы:

- использование структур для хранения данных;
- создание и включение файлов заголовков;
- декомпозирование задач при разработке и отображение их на структуры программы.

## Задание

Англо-русский словарь построен в виде массива структур `Dictionary`. Структура содержит английское слово и соответствующее ему русское слово. Для хранения записей словаря необходимо использовать динамический массив.

Разработать программу, которая:

- обеспечивает формирование словаря (добавление и удаление записей);
- записывает словарь, отсортированный по английским значениям слов, в файл;
- обеспечивает просмотр словаря;
- выполняет перевод слов с английского на русский, используя для поиска слова в словаре метод двоичного поиска в отсортированном массиве;
- выполняет перевод слов с русского на английский, используя для поиска слов в словаре метод перебора.

:::caution

Для реализации поиска по словарю **запрещено** использовать функции из стандартной библиотеки `string.h`.

:::

Программа должна обеспечивать диалог с помощью меню.

Программа должна иметь два режима запуска: **демонстрационный** и **интерактивный**:

- В **демонстрационном режиме** необходимо продемонстрировать в консоли все доступные функции работы со словарем с комментариями к отображаемым данным. В данном режиме не должно быть никакого пользовательского ввода. Исполнитель задания самостоятельно определяет какие параметры передаются в качестве аргументов в функции работы со словарем. Конечный вид данного режима определяет исполнитель задания.
- В **интерактивном режиме** обеспечить интерактивное взаимодействие с пользователем для управления словарем.

Режим запуска определять по переданным аргументам командной строки. По умолчанию программу запускать в демонстрационном режиме.

Начальное число слов в словаре равно `10`.

Для исключения проблем, связанных с вводом кириллицы, вводите русские слова латинскими буквами, например:

- `kot` - `cat`;
- `sobaka` - `dog`.

Весь функционал, обеспечивающий работу с `Dictionary`, необходимо выделить в самостоятельный модуль, состоящий из заголовочного файла `mdict.h` и файла реализации `mdict.c` или `mdict.cpp` в зависимости от используемого языка программирования. Структуру `Dictionary` необходимо объявить в `mdict.h`.

:::info

Для того, чтобы понять как создать модуль для `Dictionary`, рекомендуется обратить внимание на `CMakeLists.txt`, `mprinter.c` и `mprinter.h` из [лабораторной работы №8](./../lab8/intro.md).

:::

## Указания по выполнению работы

### Шаги разработки программы

#### I. Определение состава и способа представления исходных данных, результатов и промежуточных данных

Обратите внимание, что размер словаря неограничен. Вам необходимо использовать динамический массив для хранения записей словаря. Также на длину слова не устанавливается ограничений. Поэтом для хранения записей словаря в оперативной памяти (ОП) можно использовать структуру `Dictionary`:

```cpp
struct Dictionary {
    char *engl;    // слово по-английски
    char *rus;     // слово по-русски
};
```

Словарь хранится в текстовом файле. Элементы массива структур `Dictionary` будем записывать в файл последовательно, начиная с нулевого. При этом поля структуры записываются в виде отдельных строк, т.е. каждое слово должно заканчиваться символом `\0`.

#### II. Разработка алгоритма решения задачи

При программировании этой задачи уделим дополнительное внимание разбиению на функции и спецификации их интерфейсов. Например, логично оформить в виде функции каждую операцию со словарем (*формирование*, *поиск*, *добавление* и *удаление элемента*), поскольку они представляют собой законченные действия.

Интерфейс пользователя организуем в виде простейшего меню, которое будет выводиться на экран после каждого действия. В стандарты С/C++ не входят функции позиционирования курсора на экране, управления цветом и работы с экраном в графическом режиме, поскольку они зависят от операционной системы. Поэтому меню представим в виде пронумерованного перечня возможных действий пользователя, красиво размещенного на экране, а выбор действия будем выполнять путем ввода его номера в перечне. В функции `menu()` желательно предусмотреть реакцию на ввод пользователем непредусмотренных алгоритмом данных, например, слова вместо номера (так называемая "защита от дурака").

Будем исходить из того, что все функции должны быть независимы, чтобы изменения в одной функции не могли влиять на поведение другой. Для этого всё, что функциям необходимо получать извне, будем передавать им через параметры (за исключением нединамического массива структур `Dictionary`, который будет глобальной переменной, так как он используется всеми функциями программы).

Прежде всего определим интерфейс нашей программы. В соответствии с заданием, кажется логичным предоставить пользователю следующие возможности:

1. добавление слов в словарь;
2. удаление слов из словаря;
3. перевод слов с английского на русский;
4. перевод слов с русского на английский;
5. просмотр словаря (вывод на экран словаря из ОП);
6. вывод словаря в файл;
7. выход.

Каждый пункт этого меню, кроме последнего, оформим в виде отдельной функции. Определим прототипы предложенных функций.
Меню. Эта функция (в качестве подсказки) выводит пронумерованный перечень возможных действий пользователя и выполняет ввод номера  выбранного действия. Это число она должна вернуть в вызвавшую функцию:

```cpp
int menu();
```

Добавление слов в словарь. Чтобы добавить элемент `Dictionary` в словарь, надо задать пару слов и определить место, куда вставлять элемент, чтобы массив оставался отсортированным. Поиск места вставки и ввод добавляемого элемента выполним внутри функции, а в функцию передадим указатель на начало словаря и его размерность. Назовем ее `add_w`.

Для С:

```c
void add_w(struct Dictionary *dict, const int *n);
```

Для C++:

```cpp
void add_w(Dictionary *dict, const int *n);
```

По аналогии определите прототипы остальных функций самостоятельно.

#### III. Кодирование и тестовые примеры

В этой работе удобно использовать технологию создания программы "сверху вниз": сначала отладить главную функцию, а затем постепенно добавлять к ней остальные. На месте еще не добавленных функций обычно ставятся так называемые заглушки — функции, единственный действием которых является вывод сообщения о том, что эта функция была вызвана.

Сначала начнем с определения того, в каком режиме запускать программу.

##### Выбор режима запуска

Для того, чтобы запускать программу в интерактивном режиме, мы будем передавать в качестве аргумента символом `i`. Тогда запуск программы в интерактивном режиме будет выглядеть в оболочке Bash:

```bash
lab9 i
```

Подпрограмму, отвечающую за интерактивный режим, выделим в функцию  `interactive()`, а для демонстрационного режима - `demo()`. Тогда прототип программы, определяющий режим запуска, будет выглядеть так, как показано ниже.

Для программ на C:

```c
#include <string.h>
#include <stdbool.h>

int interactive();

int demo();

int main(int argc, char *argv[]) {
    bool isInteractive = false;    // по умолчанию демо-режим.

    // Если i передается в качестве аргумента, то программу
    // необходимо запустить в интерактивном режиме
    if ((argc == 2) && strcmp(argv[1], "i") == 0) {
        isInteractive = true;
    }

    if (isInteractive) {
        return interactive();

    } else {
        return demo();
    }
}
```

Для программ на C++:

```cpp
#include <iostream>
#include <string.h>

int interactive();

int demo();

int main(int argc, char *argv[]) {
    bool isInteractive = false;    // по умолчанию демо-режим.

    // Если i передается в качестве аргумента, то программу
    // необходимо запустить в интерактивном режиме
    if ((argc == 2) && strcmp(argv[1], "i") == 0) {
        isInteractive = true;
    }

    if (isInteractive) {
        return interactive();

    } else {
        return demo();
    }
}
```

##### Реализация интерактивного режима

При реализации подпрограммы, отвечающую за интерактивный режим, первой добавляемой функцией должна быть функция `menu()`.

При использовании меню функция `interactive()` сильно упрощается: она периодически вызывает меню, анализирует запрошенный код операции и вызывает функцию, которая выполняет эту операцию. При выборе операции с номером `7` выполнение программы завершается.

Для программ на C:

```c
int menu();

void add_w(struct Dictionary *dict, const int *n);

void print_dict(struct Dictionary *dict, const int *n);

int interactive() {
    struct Dictionary* dict;        // динамический массив структур для
                                    // хранения словаря в оперативной памяти
    int num_w = 0;                  // фактическое число записей в словаре
    while (true) {
        switch (menu()) {
            case 1:
                add_w(dict, &num_w);
                break;
            case 2:
            case 3:
            case 4:
                break;
            case 5:
                print_dict(dict, &num_w);
                break;
            case 6:
                break;
            case 7:
                return 0;
            default:
                printf("Надо вводить число от 1 до 7");
                break;
        }
    }
}
```

Для программ на C++:

```cpp
int menu();

void add_w(Dictionary *dict, const int *n);

void print_dict(Dictionary *dict, const int *n);

int interactive() {
    Dictionary* dict;               // динамический массив структур для
                                    // хранения словаря в оперативной памяти
    int num_w = 0;                  // фактическое число записей в словаре
    while (true) {
        switch (menu()) {
            case 1:
                add_w(dict, &num_w);
                break;
            case 2:
            case 3:
            case 4:
                break;
            case 5:
                print_dict(dict, &num_w);
                break;
            case 6:
                break;
            case 7:
                return 0;
            default:
                std::cout << " Надо вводить число от 1 до 7" << std::endl;
                break;
        }
    }
}
```

После отладки `menu()`, запрограммируйте и отладьте функции `add_w()` и `print_dict()`.

`add_w()` добавляет записи в массив структур, а `print_dict()` распечатывает массив из оперативной памяти.

## Проверка задания

Подготовленная программа для решения задания проверяется вручную преподавателем (визуальный контроль).

## Методический материал

1. [Требования к отчету](RequirementsForReport.md)
2. Полезная информация:
   1. [Структуры C++](UsefulInformation/StructCpp.md)
3. Контрольные вопросы:
   1. [Для потока на С](TestQuestion/ForC.md)
   2. [Для потока на С++](TestQuestion/ForCpp.md)
